Grokking Database Fundamentals for Tech Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction to Database Systems
Course Overview
Overview of Databases
Core Components of Database
Database Architectures
Relational Vs. Non-relational Databases
Data Storage in DBMS
Data Storage Fundamentals
File Organization in DBMS
Data Compression and Encoding
Quiz
Indexing in DBMS
Introduction to Database Indexes
Single Level Indexing
Tree-Based Indexing Techniques
Hash-Based Indexing
Bloom Filters
Quiz
Understanding the Transaction
Atomicity
Consistency
Isolation
Durability
Quiz
Understanding the Concurrency Control
Optimistic vs. Pessimistic Concurrency Control
Lock-Based Concurrency Control
Timestamp-Based Concurrency Control
Multiversion Concurrency Control (MVCC)
Quiz
Fundamentals of Distributed Databases
Partitioning in Databases
Partitioning Types
Sharding in Databases
Distributed Query Processing
Quiz
Replication in Databases
Replication Topologies
Understanding the Consistency Models in Databases
The CAP Theorem and Its Implications
Quiz
Understanding the Consensus
Consensus algorithms
Leader Election Strategies
Quiz
Understanding the Fault Tolerance
Logging Mechanisms in Databases
Checkpointing and Recovery Basics
Coordinated Recovery in Distributed Systems
High Availability Through Replication and Failover
Ensuring Data Resilience: Redundancy, Mirroring, and Recovery
Quiz
Introduction to NoSQL
Key-Value Stores
Document-Oriented Databases
Column-Family and Wide-Column Stores
Graph Databases
Quiz
Quora System Design & Database Design
TikTok System Design & Database Design
Airbnb System Design & Database Design
Snapchat System Design & Database Design
Hash-Based Indexing

Hash-based indexing is a technique used to store and retrieve records efficiently by mapping keys to specific locations using a hash function. Unlike tree-based indexing, which organizes data hierarchically, hash-based indexing directly maps keys to buckets or slots, making it particularly efficient for point queries.

What Is Hash-Based Indexing?

Hash-based indexing employs a hash function to compute a hash value for each key, determining the bucket or slot where the corresponding record will be stored. This eliminates the need for sequential searching, offering constant-time complexity in ideal cases.

Key Features

  • Fast and efficient for equality searches (e.g., "Find the record where ID = 102").
  • The hash function ensures even distribution of records across buckets.
  • Not suitable for range queries (e.g., finding all records with IDs between 100 and 200).

Static Hashing

In static hashing, the number of buckets is fixed when the hash table is created. Each record is mapped to a bucket based on its hash value. This structure works well when the size of the dataset is known and remains relatively constant.

How Static Hashing Works

Consider the image below.

Static Hashing
Static Hashing
  1. Data Mapping:

    • Consider the keys 98, 106, 104, and 102.
    • The hash function used is . The result of the hash function determines the bucket index.
  2. Hash Calculation:

    • → Bucket 3
    • → Bucket 1
    • → Bucket 4
    • → Bucket 2
  3. Bucket Representation:

    • Each bucket stores the actual data corresponding to the hashed key. For example:
      • Bucket 3 contains data for key 98 (e.g., John, Delhi).
      • Bucket 1 contains data for key 106.
      • Bucket 4 contains data for key 104.
      • Bucket 2 contains data for key 102.

This setup ensures efficient lookups because the hash function directly maps keys to their corresponding buckets.

Problem: What Happens When a Collision Occurs?

Now, suppose we want to add the key 103 to the hash table:

  • Bucket 3 is already occupied by key 98, leading to a collision.

Solution: Chaining

Chaining is a common method to resolve collisions. When two or more keys map to the same bucket, a linked list (or chain) is created to store multiple records in that bucket.

Chaining Example

Consider the image below.

Solving the Collision in Hashing
Solving the Collision in Hashing
  1. Collision Handling:

    • Keys 98 and 103 both map to bucket 3. Instead of overwriting data, a linked list is created within bucket 3 to store both records.
  2. How It Works:

    • The hash table is updated to include a chain for bucket 3.
    • To search for a key (e.g., 103), the hash function maps it to bucket 3, and the linked list is traversed to locate the specific record.

Chaining ensures that no data is lost due to collisions, and the hash table remains efficient.

Dynamic Hashing

Dynamic hashing, also known as extendible hashing, overcomes the limitations of static hashing by allowing the number of buckets to grow or shrink dynamically. This ensures better handling of collisions and adapts to changes in the dataset size.

How Dynamic Hashing Works

Consider the image below.

Dynamic Hashing
Dynamic Hashing
  1. Global Depth:

    • The global depth k represents the number of bits used from the hash value to determine the directory ID. For example, if ( k = 2 ), the possible directory IDs are 00, 01, 10, and 11.
  2. Mapping Keys to Buckets:

    • A hash function generates a binary hash value for each key.
    • The last ( k ) bits of the hash value determine the directory ID.
    • The directory ID points to the corresponding bucket where the record is stored.
  3. Handling Bucket Overflow:

    • If a bucket overflows (e.g., due to multiple keys hashing to the same bucket), bucket splitting occurs:

      • The overflowing bucket is split into two new buckets.
      • The global depth k increases, and the directory is updated to reflect the new buckets.
    • For example, if ( B_2 ) overflows, the directory IDs are updated to 100 and 101, and the bucket splits to redistribute the records.

    • Keys are redistributed between the new buckets based on their updated hash values.

Properties of Dynamic Hashing

  1. Bucket Splitting: When a bucket overflows, it is split into two, and the keys are redistributed.
  2. Dynamic Directory: The directory grows or shrinks as needed, ensuring efficient data storage and retrieval.
  3. Flexibility: The hash function dynamically adjusts to prevent collisions and ensure balanced bucket utilization.

Dynamic hashing provides a scalable and efficient solution for managing large and dynamic datasets.

Comparison of Static and Dynamic Hashing

FeatureStatic HashingDynamic Hashing
Number of BucketsFixedGrows or shrinks dynamically
Collision HandlingChaining or open addressingBucket splitting with updated directories
FlexibilityLimitedHighly flexible
Use CasesSmall, stable datasetsLarge, dynamic datasets

Tree-Based Indexing Techniques
Bloom Filters
Mark as Completed

On this page

What Is Hash-Based Indexing?

Key Features

Static Hashing

How Static Hashing Works

Problem: What Happens When a Collision Occurs?

Solution: Chaining

Dynamic Hashing

How Dynamic Hashing Works

Properties of Dynamic Hashing

Comparison of Static and Dynamic Hashing